The present disclosure relates to updating cache devices, and more specifically, but not exclusively, to updating cache devices using two Bloom filters.
A Bloom filter is a space-efficient probabilistic data structure that is used to test whether a particular element is a member of a set. False positive matches are possible, but false negatives are not, that is, a query returns either “possibly in set” or “definitely not in set.”
An empty Bloom filter is a bit array of “m” bits set to “0.” There must also be “k” different hash functions defined, each hash function hashes some set element to one of the “m” array positions, generating a uniform random distribution. Typically, “k” is a constant much smaller than “m,” which is proportional to the number of elements to be added. The precise choice of “k” and the constant of proportionality of “m” are determined by the intended false positive rate of the filter.